package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class isSymmetric_101 {

    /**
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。

     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        /**
         * 验证轴对称，所以采用中序遍历合适
         * 有两个测试用例过不去，太逆天的用例，从左向右，和从右向左竟然一模一样
         */
    function1(root.left);
        return function2(root.right) && k1==k2;
    }
    List<Integer>num=new ArrayList<>();
    int k1=1;
    int k2=1;
    void function1(TreeNode node){
        if (node == null) {
            num.add(-1);
            k1++;
            return;
        }
        if(node.left!=null || node.right!=null)
            function1(node.left);
        num.add(node.val);
        k1++;
        if(node.left!=null || node.right!=null)
            function1(node.right);
    }
    boolean function2(TreeNode node){
        if(node==null){
            //进行判断
            return num.get(k2++ - 1) == -1;
        }
        boolean ans=true;
        if(node.left!=null || node.right!=null)
            ans=function2(node.right);  //因为轴对称，从右向左
        if (num.get(k2++ - 1) != node.val) //进行判断
            return false;
        if(node.left!=null || node.right!=null)
            ans=ans && function2(node.left);  //若右边无法匹配，即ans值为false，直接返回ans，不用进入左边递归
        return ans;
    }


    /**
     * 官解的递归100%
     * 关键思路
     * 左子树 2 的左孩子 == 右子树 2 的右孩子
     * 左子树 2 的右孩子 == 右子树 2 的左孩子
     */
    public boolean isSymmetric2(TreeNode root) {
        if(root==null) {
            return true;
        }
        //调用递归函数，比较左节点，右节点
        return dfs(root.left,root.right);
    }

    boolean dfs(TreeNode left, TreeNode right) {
        //递归的终止条件是两个节点都为空
        //或者两个节点中有一个为空
        //或者两个节点的值不相等
        if(left==null && right==null)
            return true;
        if(left==null || right==null)
            return false;
        if(left.val!=right.val)
            return false;
        //关键思路
        //递归的比较 左节点的左孩子 和 右节点的右孩子
        //以及比较  左节点的右孩子 和 右节点的左孩子
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }
}
